import dis from '../data/distance.json'
import { _Cache } from './cache'

export const MAX_STEP = 100
const POOL_STORE = 100
const SEQ_SIZE = 31
const TOURNA_SIZE = 30
const BREED_PATTERN = [
    {
        start: 0,
        end: 3,
    },
    {
        start: 12,
        end: 18,
    },
    {
        start: 25,
        end: 29,
    }
]
const MUTATION_PATTERN = [
    {
        from: 6,
        to: 9,
    },
    {
        from: 1,
        to: 18,
    },
    {
        from: 21,
        to: 26
    },
    {
        from: 1,
        to: 7
    }
]
/**
 * 锦标赛选择15个父代进行遗传
 * 与其他父代交叉生成15个子代并变异。
 * 最后在15+60个后代中筛选出60个。
 */

export class Evolution {

    bestSeq: number[]

    cnt: number

    pool: number[][]

    cache: _Cache<number[], number>

    winners: number[][]

    sons: number[][]

    worst: number

    avg: number

    constructor(initSeq: number[]) {
        this.bestSeq = initSeq
        this.cnt = 0
        this.pool = []
        this.cache = new _Cache()
        //创建繁殖池
        this.buildPool()

    }

    private rand(bias: number, scale: number): number {
        return Math.round(Math.random()*(scale - 1) + bias)
    }

    private buildPool() {
        const ramdomSeq = (seq: number[]) => {
            const swapCnt = this.rand(3, 2)
            let posGabage: number[] = []

            const uniquePos = () => {
                let temPos = -1
                do {
                    temPos = this.rand(0, SEQ_SIZE)
                } while(temPos === -1 || posGabage.includes(temPos))
                posGabage.push(temPos)
                return temPos
            }
            let s = [...seq]
            // console.log('before all change', s, seq)
            for(let i = 0; i < swapCnt; i++) {
                let pos1 = uniquePos(),
                    pos2 = uniquePos(),
                    t = s[pos2]
                // console.log('before change', s)
                // console.log('change pos', pos1, pos2)
                // console.log('gen pool', pos1, pos2)
                s[pos2] = s[pos1]
                s[pos1] = t
                // console.log('after change', s)
            }
            return s
        }
        let seq = [...this.bestSeq]
        for(let i = 0; i < POOL_STORE; i++) {
            this.pool.push(seq)
            seq = ramdomSeq(seq)
        }
    }

    private getDis(seq: number[]) {
        let dist = 0
        for(let i = 0; i < seq.length; i++) {
            let j = i + 1 == seq.length ? 0 : i + 1
            dist += dis[seq[i]][seq[j]]
        }
        return dist
    }

    private readFromCache(seq: number[]) {
        return this.cache.readOrSet(seq, () => this.getDis(seq))
    }

    private bestSelect(): this {
        this.winners = this.pool.sort((a, b) => this.readFromCache(b) - this.readFromCache(a)).slice(0, TOURNA_SIZE)
        this.pool = this.pool.filter(seq => !this.winners.includes(seq))
        return this
    }

    private tournament(): this {
        this.winners = []
        for(let i = 0; i < TOURNA_SIZE; i++) {
            let pos1 = this.rand(0, POOL_STORE),
                pos2 = pos1
            while(pos2 === pos1) {
                pos2 = this.rand(0, POOL_STORE)
            }

            let dis1 = this.readFromCache(this.pool[pos1]),
                dis2 = this.readFromCache(this.pool[pos2]),
                winner = dis1 < dis2 ? this.pool[pos1] : this.pool[pos2]
            
                if(this.winners.includes(winner)) {
                    i--
                    continue
                }
            this.winners.push(winner)
        }

        //过滤一便pool
        this.pool = this.pool.filter(seq => !this.winners.includes(seq))
        return this
    }

    //winner和其他产生后代
    private crossover(): this {
        //生成两个孩子选最优
        const breed = (father: number[], mother: number[]) => {
            //交换基因
            let son1 = [...father],
                son2 = [...mother]
            for(let i = 0; i < BREED_PATTERN.length; i++) {
                let { start, end } = BREED_PATTERN[i]
                let subOfFa = son1.slice(start, end),
                    subOfMa = son2.slice(start, end)
                
                son1 = son1.slice(0, start).concat(subOfMa).concat(son1.slice(end, son1.length)),
                son2 = son2.slice(0, start).concat(subOfFa).concat(son2.slice(end, son2.length))
                    
            }
            // console.log('father', father)
            //去重并置换
            // console.log('before filter', son1)
            son1 = son1.filter((val, index, arr) => arr.indexOf(val, 0) === index)
            // console.log('after filter', son1)
            son1 = son1.concat(father.filter(val => !son1.includes(val)))
            // console.log('concat', son1)
            son2 = son2.filter((val, index, arr) => arr.indexOf(val, 0) === index)
            son2 = son2.concat(mother.filter(val => !son2.includes(val)))

            let dis1 = this.readFromCache(son1),
                dis2 = this.readFromCache(son2)

            return dis1 < dis2 ? son1 : son2

        }
        this.sons = []
        for(let i = 0; i < TOURNA_SIZE; i++) {
            let wife = this.pool[this.rand(0, POOL_STORE - TOURNA_SIZE)]
            this.sons.push(breed(this.winners[i], wife))
        }

        // console.log(this.sons)
        return this
    } 

    //变异
    private mutation(): this {
        for(let i = 0; i < TOURNA_SIZE; i++) {
            let { from, to } = MUTATION_PATTERN[this.rand(0, MUTATION_PATTERN.length)]
            let temp = this.sons[i][from]
            this.sons[i][from] = this.sons[i][to]
            this.sons[i][to] = temp
        }
        return this
    }

    private merge(): this {
        this.pool = this.pool.concat(this.sons)
        return this
    }

    private setBestSeq() {
        let sortedPool = this.pool.sort((a, b) => this.readFromCache(a) - this.readFromCache(b))
        this.bestSeq = [...sortedPool[0]]
        this.worst = this.readFromCache(sortedPool[POOL_STORE - 1])

        this.avg = 0
        for(let i = 0; i < POOL_STORE; i++) {
            this.avg += this.readFromCache(this.pool[i])
        }
        this.avg = Math.round(this.avg / POOL_STORE)
    }

    //算法主进程
    private mainProc() {
        //锦标赛规则
        // this.tournament().crossover().mutation().merge().setBestSeq()
        this.bestSelect().crossover().mutation().merge().setBestSeq()
    }

    //迭代器
    public *iter() {
        while(this.cnt <= MAX_STEP) {
            this.cnt++
            this.mainProc()
            yield {
                bestSeq: this.bestSeq,
                cnt: this.cnt,
                best: this.getDis(this.bestSeq),
                avg: this.avg,
                worst: this.worst
            }
        }
    }

    public reset() {
        this.cnt = 0
        this.sons = []
        this.winners = []
    }
}
